package 动态规划;

public class Ch09_01背包问题迭代 {
    public static void main(String[] args) {
        int[] w={71,69,1};   //重量
        int[] c={100,1,2}; //价值
        int capacity=70;
        System.out.println(maxKnapsack(w,c,capacity));
    }

    public static int maxKnapsack(int[] w,int[] c,int capacity){
        if (capacity<=0){
            return 0;
        }
        /**
         * dp[i][j] 表示 在容量为 i，有j件物品可选择的情况下能拿的最大价值
         */
        int[][] dp=new int[capacity+1][w.length+1];
        for (int i=1;i<=capacity;i++){
            for (int j=1;j<dp[0].length;j++){
                int select=i>=w[j-1]?dp[i-w[j-1]][j-1]+c[j-1]:0;
                int noSelect=dp[i][j-1];
                dp[i][j]=Math.max(select,noSelect);
            }
        }
        return dp[capacity][w.length];
    }
}
